package codeRandomThoughts.Test56合并区间;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public int[][] merge(int[][] intervals) {
        //对intervals按照start升序排序
        Arrays.sort(intervals, (i1, i2) -> {
            return Integer.compare(i1[0], i2[0]);
        });

        List<int[]> result = new ArrayList<>();
        int start = -1;
        int end = -1;
        for (int[] interval : intervals) {
            //如果和上一个区间有交叉
            if (interval[0] <= end) {
                //合并两个区间
                end = Math.max(end, interval[1]);
            } else {
                //和前一个区间没有交叉
                //把start和end添加到结果中
                result.add(new int[]{start, end});
                start = interval[0];
                end = interval[1];
            }
        }

        result.add(new int[]{start, end});
        result.remove(0);

        return result.toArray(new int[result.size()][]);
    }
}
